package com.leetcode.周赛.第84场;

import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;

/**
 * @author: xiaomi
 * @date: 2021/1/18
 * @description: 833. 字符串中的查找与替换
 * https://leetcode-cn.com/problems/find-and-replace-in-string/
 */
public class B_833_字符串中的查找与替换 {

    public static void main(String[] args) {
        String str = "abcd";
        int[] indexes = new int[]{0, 2};
        String[] sources = new String[]{"a", "cd"};
        String[] targets = new String[]{"eee", "ffff"};
        B_833_字符串中的查找与替换 action = new B_833_字符串中的查找与替换();
        String replaceString = action.findReplaceString(str, indexes, sources, targets);
        System.out.println("replaceString = " + replaceString);
    }

    /**
     * 似乎没有什么奇技淫巧
     * --
     * 重新审了一遍，发现顺序找 indexes ，由于替换后的位置会发生变动，所以无法方便地同时找到并替换。
     * 那么只能从逆序地找了。
     * 但是原来不是有序的，需要先排序 -> 需要同时保证 sources 和 target 顺序对称
     * @param S
     * @param indexes
     * @param sources
     * @param targets
     * @return
     */
    public String findReplaceString(String S, int[] indexes, String[] sources, String[] targets) {
        int len = S.length();
        if (S == null || S.length() == 0) {
            return S;
        }
        //value -index // 由于不会重复
        HashMap<Integer, Integer> map = new HashMap<>();

        //建立一个大顶堆
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for (int i = indexes.length-1; i >=0; i--) {
            map.put(indexes[i], i);
            queue.offer(indexes[i]);
        }
        while (!queue.isEmpty()){
            int index= map.get(queue.poll());
            S = findReplace(S, len, indexes[index], sources[index], targets[index]);
            len = S.length();
        }

        return S;

    }


    private String findReplace(String str, int len, int index, String source, String target) {
        boolean flag = true;
        int sourceLen = source.length();
        for (int i = 0; i < source.length(); i++) {
            int sIndex = index + i;

            if (sIndex >= len || str.charAt(sIndex) != source.charAt(i)) {
                flag = false;
                break;
            }
        }
        if (flag) {
            //如果是确认进行替换的
            return str.substring(0, index) + target + str.substring(index + sourceLen);
        }
        return str;
    }


}
